package algorithm.sort;

/**
 * 荷兰旗问题
 * 给定一个整数数组，给定一个值K，这个值在原数组中一定存在，
 * 要求把数组中小于K的元素放到数组的左边，
 * 大于K的元素放到数组的右边，
 * 等于K的元素放到数组的中间，
 * 最终返回一个整数数组，其中只有两个值，
 * 分别是等于K的数组部分的左右两个下标值。
 *
 */
public class NetherlandsFlag {
    public int[] partition(int[] arr, int l, int r, int num) {
        int less = l - 1;
        int more = r + 1;
        int cur = l;
        while (cur < more) {
            if (arr[cur] < num) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > num) {
                swap(arr, --more, cur);
            } else {
                cur++;
            }
        }
        return new int[]{less + 1,more -1};
    }

    public void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
